Back to course home
0% completed
Vote For New Content
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Problem Statement
You are given a positive integer n. You are also given undirected graph containing 0 to n - 1 nodes, and 2D integer array edges where edges[i] = [ai, bi] denotes that there exists an undirected edge connecting nodes ai and bi.
Return the count of unique node pairs where there's no path from one node to another.
Examples
Example 1:
- Input:
n = 4, edges = [[0, 1], [2, 3]]
- Expected Output: 4
- Justification: The graph is divided into two disconnected parts: nodes 0 and 1 are connected, and nodes 2 and 3 are connected. The unreachable pairs are (0, 2), (0, 3), (1, 2), and (1, 3).
Example 2:
- Input:
n = 5, edges = [[0, 1], [2, 3]]
- Expected Output: 8
- Justification: The unreachable pairs are (0, 2), (0, 3), (1, 2), (1, 3), (0, 4), (1, 4), (2, 4), and (3, 4).
Example 3:
- Input:
n = 3, edges = [] - Expected Output: 3
- Justification: With no edges, every node is isolated. Hence, all possible pairs are unreachable from each other: (0, 1), (0, 2), and (1, 2).
Try it yourself
Try solving this question here:
Java
Saved to Cloud
. . . .
Solution: Minimum Area Rectangle
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Mark as Completed
On this page
Problem Statement
Examples
Try it yourself